Міністерство науки і освіти України.
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій.
Кафедра ПЗ
Звіт
До лабораторної роботи №6
За курсом «Алгоритми і структури даних».
Виконав
студент групи ПІ 1
Львів 2007
Тема роботи: Ознайомлення із методами сортування, та порівняння їх швидкодії.
Мета роботи: Вивчити та дослідити методи сортування, обробки даних. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по сортуванню: бульбашкою, вставкою, методом Шела, швидким методом.
Код програми
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
//---------------------------------------------------------------------------
void Shell_sort( int a[], int n )
{
int z,step,i,j,tmp;
for( step = n/2 ; step>0 ; step >>= 1){
for( i=0; i<(n-step); ++i ){
j = i;
while ( (j>=0) && (a[j]>a[j+step]) )
{
tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}}}}
//---------------------------------------------------------------------------
void zluttja (int N[], int mas2[],int n)
{
int d,j,a1,a2,a3,f;
for ( d=1;d<n;d*=2)
{
for( j=0;j<n;j+=d*2)
{
a1=j;
a2=j+d;
a3=j;
while((a1-j<d&&a1<n)||
(a2-j-d<d&&a2<n))
if(a1-j>=d||a1>=n)
mas2[a3++]=N[a2++];
else if(a2-j-d>=d||a2>=n)
mas2[a3++]=N[a1++];
else
mas2[a3++]=(N[a1]<=N[a2])?N[a1++]:N[a2++];
}
for( f=0;f<n;f++)
N[f]=mas2[f];
}
}
//---------------------------------------------------------------------------
void bulbashka(int N[], int d)
{
int k,l,tmp;
for (k=0;k<d-1;k++)
for (l=0;l<d-k-1;l++)
if (N[l+1]<N[l])
{
tmp=N[l];
N[l]=N[l+1];
N[l+1]=tmp;
}
}
//---------------------------------------------------------------------------
void vstavka (int N[], int d)
{
int k,l,r,tmp;
for (k=0;k<d-1;k++)
{ r=k; tmp=N[k];
for (l=k+1;l<d;l++)
if (N[l]<tmp)
{
r=l;
tmp=N[l];
}
N[r]=N[k];
N[k]=tmp;
}
}
//---------------------------------------------------------------------------
int partition (int m[], int a, int b)
{
int i=a,j,t;
for ( j=a; j<=b; j++)
{
if (m[j] <= m[b])
{
t = m[i];
m[i] = m[j];
m[j] = t;
i++;
}
}
return i-1;
}
void quicksort (int m[], int a, int b)
{
int c;
if (a >= b) return;
c = partition (m, a, b);
quicksort (m, a, c-1);
quicksort (m, c+1, b);
}
//---------------------------------------------------------------------------
int verify(int N[], int d)
{
int k;
for (k=0;k<d-1;k++)
if (N[k]>N[k+1])
return 0;
return 1;
}
//---------------------------------------------------------------------------
void main(void)
{
int N[100000],M[100000];
int i,j,m;
int C[5]={10000,20000,50000,80000,100000};
clock_t start, end;
clrscr();
printf ("Enter the method \n");
scanf ("%i",&m);
if ((m>5)||(m<1))
puts("Wrong nunber of the method");
for (i=0;i<5;i++)
{
for (j=0;j<C[i];j++)
N[j]=rand();
switch (m)
{
case 1: start=clock();
bulbashka(N, C[i]);
end=clock();
break;
case 2: start=clock();
vstavka (N, C[i]);
end=clock();
break;
case 3 : start=clock();
zluttja (N,M,C[i]);
end=clock();
break;
case 4 : start=clock();
Shell_sort (N,C[i]);
end=clock();
break;
case 5 : start=clock();
quicksort (N,0,C[i]-1);
end=clock();
break;
}
printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error");
}
getch();
}
Протокол роботи програми:
Сортування бульбашкою Сортування вставкою
Сортування злиттям Метод...
